package com.hspedu.newData.dmsxl.树.二叉树的遍历.层序遍历迭代法.队列;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-04-23 
 * @Version: 1.0
 */

public class LC116填充每个节点的下一个右侧节点指针 {

    // todo
    // 效率很低,题目中是完全二叉树，可以利用到这个特性，前序遍历的同时，将左节点指向右节点。
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();

        queue.offer(root);

        while(!queue.isEmpty()){

            int len = queue.size();
            while(len > 0){
                Node node = queue.poll();
                if (len != 1){
                    node.next = queue.peek();
                }

                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);

                len --;
            }
        }
        return root;
    }


    // todo 递归的方式还不太会写，是这个思路，但是要考虑递归的条件
    public Node connect1(Node root) {
        if (root == null || root.left == null) {
            return root;
        }

        root.left.next = root.right;
        connect1(root.left);
        connect1(root.right);
        return root;
    }
}


class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
